package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 1049. 最后一块石头的重量 II https://leetcode.cn/problems/last-stone-weight-ii
 * 题目简述：一堆石头每次选两块进行粉碎，若这两块石头重量相等则都粉碎消失，若不等则剩余一块重量为差值的小石头返回石头堆，问最后剩余的石头的最小重量
 * todo 题集 https://leetcode.cn/problems/last-stone-weight-ii/solutions/805162/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-5lfv/
 */
public class LastStoneWeightII {

    public static void main(String[] args) {
        System.out.println(new LastStoneWeightII().lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));
    }

    /**
     * 思路：01背包-最大价值问题。假设最优解的方案为: (a -b) -(c -(d - e))，展开即为: a -b- c + d -e。可以想到，碰撞的最后结果即为不重复地取所有数相加减得到的值
     *      ，即一部分数减去另一部分数的结果，因此当一个子集最接近sum/2时，可算得碰撞最小值，转化为背包问题，即sum/2大小背包能装下的最大的子集和。
     * 1. 定义dp：dp[j]为背包容量为j时能获取的最大价值总和
     * 2. 状态转移公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0;i < stones.length;i++) {
            sum += stones[i];
        }
        int w = sum/2;
        int[] dp = new int[w+1];
        for (int i = 0;i < stones.length;i++) {
            for (int j = w;j >= stones[i];j--) {//背包容量要大于等于物品i的重量
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2*dp[w];
    }

}
